using System.Collections.Generic;
using System;
using Tao.OpenGl;


namespace cs5643.rigidbody
{
    
    using System.Drawing;
    /**
     * Converts an image into Block objects, and identifies connected
     * components to generate RigidBody objects.  
     * 
     * NOTE: YOU DON'T HAVE TO (or want to!) MODIFY THIS CODE.
     * 
     * @author Doug James, March 2007.
     */
    public class ImageBlocker
    {
        /** Image in question. */
        static Bitmap image;

        /** #Rows */
        static int M;
        /** #Columns */
        static int N;

        /** Block[i,j] with null for massless/background Blocks. */
        static Block[,] B;

        /** Resulting sets of connected Block components. */
        static List<HashSet<Block>> components = new List<HashSet<Block>>();

        /**
         *
         *
         * @param tgaFilename TGA image filename (RGB, uncompressed)
         * containing rigid image elements on a white background.
         */
        public ImageBlocker(String tgaFilename)
        {
            image = loadImage(tgaFilename);

            buildBlocks();

            findConnectedComponents();
        }

        /** Nonempty Blocks of image. */
        public List<Block> getBlocks()
        {
            List<Block> all = new List<Block>();
            for (int i = 0; i < M; i++)
            {
                for (int j = 0; j < N; j++)
                {
                    if (B[i,j] != null) all.Add(B[i,j]);
                }
            }
            return all;
        }

        /** Constructs new RigidBody objects for each connected component
         * of Blocks, and adds each to the RigidBodySystem. */
        public void AddComponentRigidBodies(RigidBodySystem R)
        {
            foreach (HashSet<Block> cc in components)
                R.add(new RigidBody(cc));
        }

        private void findConnectedComponents()
        {
            //CCBuilder ccb = new CCBuilder();
            ScanlineCCBuilder ccb = new ScanlineCCBuilder();
        }

        //     /** 
        //      * Finds connected components. 
        //      * @deprecated SLOW! ... use scanline version with expansion
        //      * moves.
        //      */
        //     class CCBuilder
        //     {
        // 	HashSet<Block> remainingBlocks = new HashSet<Block>();

        // 	CCBuilder() 
        // 	{
        // 	    remainingBlocks.AddAll(getBlocks());

        // 	    /// FIND CONNECTED COMPONENTS:
        // 	    Console.Out.WriteLine("\nFINDING CONNECTED COMPONENTS...");
        // 	    while(remainingBlocksCount > 0) {/// FIND A CONNECTED COMPONENT:
        // 		Block block = remainingBlocks.iterator().next();
        // 		HashSet<Block> cc = findCC(block);
        // 		remainingBlocks.removeAll(cc);
        // 		components.Add(cc);
        // 		Console.Out.WriteLine("   |COMPONENT| = "+ccCount); 

        // 	    }
        // 	    Console.Out.WriteLine("FOUND "+componentsCount+" CONNECTED COMPONENTS");
        // 	}

        // 	HashSet<Block> findCC(Block root)
        // 	{
        // 	    HashSet<Block> cc       = new HashSet<Block>();
        // 	    HashSet<Block> frontier = new HashSet<Block>();

        // 	    frontier.Add(root);
        // 	    HashSet<Block> neighbors = new HashSet<Block>();
        // 	    while(frontierCount > 0) {
        // 		Block block = frontier.iterator().next();//sloth

        // 		// ADD BLOCK:
        // 		cc.Add(block);
        // 		frontier.remove(block);

        // 		// EXPAND NEIGHBORS:
        // 		addBlockNeighbors(block, neighbors);
        // 		neighbors.removeAll(cc);///guarantees neighbors are new (sloth)
        // 		frontier.AddAll(neighbors);
        // 	    }

        // 	    return cc;
        // 	}

        // 	void addBlockNeighbors(Block block, Collection<Block> addToMe) //, Set<Block> removeFromMe)
        // 	{
        // 	    int I = block.i;
        // 	    int J = block.j;
        // 	    for(int i=Math.Max(0,I-1); i<=Math.Min(I+1,M-1); i++) {
        // 		for(int j=Math.Max(0,J-1); j<=Math.Min(J+1,N-1); j++) {
        // 		    if(B[i,j] != null) {
        // 			addToMe.Add(B[i,j]);
        // 			//removeFromMe.remove(B[i,j]);
        // 		    }
        // 		}
        // 	    }
        // 	    addToMe.remove(block);
        // 	    //removeFromMe.remove(block);
        // 	}
        //     }

        /** 
         * Finds connected components by unifying row/column fragment
         * labels via iterative minimization of row/col fragment
         * labels using expansion moves.
         */
        class ScanlineCCBuilder
        {
            private List<RowFrag>[] rowFrag; // of Frag
            private List<ColFrag>[] colFrag; // of Frag
            static private int[,] label;

            public ScanlineCCBuilder()
            {
                /// FIND CONNECTED COMPONENTS:
                Console.Out.WriteLine("\nFINDING CONNECTED COMPONENTS...");

                buildRowFragments();// --> rowFrag[i]
                buildColFragments();// --> colFrag[j]

                minimizeConnectedLabels();

                extractComponents(); // --> components

                Console.Out.WriteLine("FOUND " + components.Count + " RIGID BODIES");
            }

            /** Iterative minimization of connected labels using
             * alternating row/column fragment minimization. */
            public void minimizeConnectedLabels() 
	{
	    /// INITIALIZE LABELS: 
	    label = new int[M,N];
	    for(int i=0; i<M; i++) 
		for(int j=0; j<N; j++) 
		    label[i,j] = Int32.MaxValue;

	    /// INIT TO ROW FRAG/COMPONENT LABELS:
	    int fragCount = 0;
	    for(int i=0; i<M; i++) {
		List<RowFrag> frags = rowFrag[i];
		foreach (RowFrag frag in frags) {
		    foreach (Block block in frag.getBlocks()) {
			label[block.i,block.j] = fragCount;
		    }
		    fragCount++;
		}
	    }

	    /// ITERATE ROW/COLUMN LABEL MINIMIZATION (a simple
	    /// "expansion move" ... a fun thing to do at Cornell):
	    int nChangesThisIteration = 1;
	    while(nChangesThisIteration > 0) {/// STOP IF EXPANSION
					      /// MOVE HAS NO CHANGES
		nChangesThisIteration = 0;

		/// ROW EXPANSION:
        foreach (List<RowFrag> frags in rowFrag)
        {
            foreach (RowFrag frag in frags)
            {
                int minLabel = frag.getMinLabel();
                bool changed = frag.setMinLabel(minLabel);
                if (changed) nChangesThisIteration++;
            }
        }

		/// COL EXPANSION:
		foreach(List<ColFrag> frags in colFrag) {
		    foreach(ColFrag frag in frags) {
			int     minLabel = frag.getMinLabel();
			bool changed  = frag.setMinLabel(minLabel);
			if(changed) nChangesThisIteration++;
		    }
		}

		Console.Out.WriteLine("ITERATE: #label changes = "+nChangesThisIteration);
	    }
	}

            /** Extracts "components" from label */
            void extractComponents()
            {
                // MAP label-->blocks
                Dictionary<int, HashSet<Block>> map = new Dictionary<int, HashSet<Block>>();

                for (int i = 0; i < M; i++)
                {
                    for (int j = 0; j < N; j++)
                    {
                        int lab = label[i,j];
                        if (lab < Int32.MaxValue)
                        {//valid label:
                            HashSet<Block> comp;
                            if(map.ContainsKey(lab)){
                                comp = map[lab];
                            } else{
                                comp = new HashSet<Block>();
                                map[lab] = comp;
                            }
                            comp.Add(B[i, j]);
                            
                        }
                    }
                }

                // EXTRACT COMPONENTS:
                HashSet<HashSet<Block>> values = new HashSet<HashSet<Block>>();
                values.UnionWith(map.Values);
                foreach (HashSet<Block> set in values)
                {
                    components.Add(set);
                }
            }

            void buildColFragments()
	{
	    colFrag = new List<ColFrag>[N];

 	    Console.Out.Write("BUILDING COL FRAGMENTS ");
	    int count = 0;
	    for(int j=0; j<N; j++) {
		colFrag[j] = new List<ColFrag>();

 		ColFrag fragment = null;
		for(int i=0; i<M; i++) {
 		    if(B[i,j] == null) {
 			fragment = null;
 		    }
 		    else {
 			if(fragment==null)   {
			    fragment = new ColFrag(j);
			    colFrag[j].Add(fragment);
			    count++;
			}

 			fragment.Add(B[i,j]);
 		    }
 		}
 		if(j%(N/10)==0) Console.Out.Write(".");
 	    }
 	    Console.Out.WriteLine(" DONE ("+count+" col fragments)");
	}

            void buildRowFragments()
	{
	    rowFrag = new List<RowFrag>[M];

 	    Console.Out.Write("BUILDING ROW FRAGMENTS ");
	    int count = 0;
 	    for(int i=0; i<M; i++) {
		rowFrag[i] = new List<RowFrag>();

 		RowFrag fragment = null;
 		for(int j=0; j<N; j++) {
 		    if(B[i,j] == null) {
 			fragment = null;
 		    }
 		    else {
 			if(fragment==null)   {
			    fragment = new RowFrag(i);
			    rowFrag[i].Add(fragment);
			    count++;
			}

 			fragment.Add(B[i,j]);
 		    }
 		}
		if(rowFrag[i].Count > 0) Console.Out.Write(" "+rowFrag[i].Count+" ");
 		if(i%(M/10)==0) Console.Out.Write(".");
 	    }
 	    Console.Out.WriteLine(" DONE ("+count+" row fragments)");
	}

            class RowFrag
            {
                List<Block> blocks = new List<Block>();
                int index;

                ///index=i
                public RowFrag(int index) { this.index = index; }

                public void Add(Block block) { blocks.Add(block); }

                public List<Block> getBlocks() { return blocks; }

                public int getMinLabel()
                {
                    int min = Int32.MaxValue;
                    foreach (Block block in blocks)
                    {
                        int j = block.j;
                        min = Math.Min(min, label[index,j]);
                        if (index > 0)
                        {//Check previous row too (faster propagation)
                            min = Math.Min(min, label[index - 1,j]);
                            /// NOTE: Effectively ignores B=null entries, since
                            /// they have label=Int32.MaxValue

                            if (j > 0) min = Math.Min(min, label[index - 1,j - 1]);
                            if (j + 1 < N) min = Math.Min(min, label[index - 1,j + 1]);
                        }

                        // 		    if(index+1 < M) {//Check previous row too (faster propagation)
                        // 			min = Math.Min(min, label[index+1,j]);
                        // 			/// NOTE: Effectively ignores B=null entries, since
                        // 			/// they have label=Int32.MaxValue

                        // 			if(j>0)   min = Math.Min(min, label[index+1,j-1]);
                        // 			if(j+1<N) min = Math.Min(min, label[index+1,j+1]);
                        // 		    }
                    }
                    return min;
                }

                /**
                 * @return True if some values changed.
                 */
                public bool setMinLabel(int min)
                {
                    bool changed = false;
                    foreach (Block block in blocks)
                    {
                        if (label[index,block.j] != min) changed = true;
                        label[index,block.j] = min;
                    }
                    return changed;
                }
            }

            /** Col impl of Frag */
            public class ColFrag
            {
                List<Block> blocks = new List<Block>();
                int index;//col

                public ColFrag(int index) { this.index = index; }

                public void Add(Block block) { blocks.Add(block); }

                public List<Block> getBlocks() { return blocks; }

                public int getMinLabel()
                {
                    int min = Int32.MaxValue;
                    foreach (Block block in blocks)
                    {
                        int i = block.i;
                        min = Math.Min(min, label[i,index]);
                        if (index > 0)
                        {//Check previous col too (faster propagation)
                            min = Math.Min(min, label[i,index - 1]);
                            /// NOTE: Effectively ignores B=null entries, since
                            /// they have label=Int32.MaxValue

                            if (i > 0) min = Math.Min(min, label[i - 1,index - 1]);
                            if (i + 1 < M) min = Math.Min(min, label[i + 1,index - 1]);
                        }

                        if (index + 1 < N)
                        {
                            min = Math.Min(min, label[i,index + 1]);
                            if (i > 0) min = Math.Min(min, label[i - 1,index + 1]);
                            if (i + 1 < M) min = Math.Min(min, label[i + 1,index + 1]);
                        }



                    }
                    return min;
                }

                public bool setMinLabel(int min)
                {
                    bool changed = false;
                    foreach (Block block in blocks)
                    {
                        if (label[block.i,index] != min) changed = true;
                        label[block.i,index] = min;
                    }
                    return changed;
                }
            }//ColFrag
        }

        /** Builds nonwhite blocks. */
        private void buildBlocks()
    {
	//int nx = ; 
        M = image.Height;
        N = image.Width;
	B = new Block[M,N];

	int maxMN = (int)Math.Max(M,N);
	double  h = 0.5/(double)maxMN;//halfwidth 
	//ByteBuffer bytes = image.getData();
	//bytes.rewind();
	int nnz = 0;
	for(int i=0; i<M; i++) {
	    for(int j=0; j<N; j++) {
		double  x = h*(2*j + 1);
		double  y = h*(2*i + 1);
		Pnt2D p = new Pnt2D(x,y);
		//Pnt3F c = nextColor(bytes);
            Color co = image.GetPixel(j,i);
            Pnt3F c = new Pnt3F(co.R / 255.0f, co.G / 255.0f, co.B / 255.0f);

		/// RECORD MASSIVE BLOCKS:
		Block block = new Block(i, j, c, p, h);
		if(block.getColorMass() > 0.01) {
		    B[i,j] = block;
		    nnz++;
		}
	    }
	}
	Console.Out.WriteLine("Built "+nnz+" blocks / "+(M*N)+" or "+((float)nnz/(float)(M*N)*100.0f)+"%");
    }

        private static Bitmap loadImage(String tgaFilename)
        {
            Bitmap image = Paloma.TargaImage.LoadTargaImage(tgaFilename);
            image.RotateFlip(RotateFlipType.RotateNoneFlipY); //tga upside down
            //TGAImage image = TGAImage.read(tgaFilename);
            Console.Out.WriteLine("image('" + tgaFilename + "'): height=" + image.Height + " width=" + image.Width);

            //if (image.getGLFormat() != Gl.GL_BGR_EXT)
            //    throw new Exception("Only BGR TGA formats accepted.");

            return image;
        }


        /** Parses next BGR triple. */
        //private static Pnt3F nextColor(ByteBuffer bytes)
        //{
        //    float b = nextChannel(bytes);
        //    float g = nextChannel(bytes);
        //    float r = nextChannel(bytes);
        //    return new Pnt3F(r, g, b);
        //}
        //private static float nextChannel(ByteBuffer bytes)
        //{
        //    int r = (int)bytes.get();
        //    r = (r + 256) % 256;
        //    float x = (float)r / 255.0f;
        //    if (x > 1.0f) x = 1.0f;
        //    if (x < 0.0f) x = 0.0f;
        //    //Console.Out.WriteLine("r = "+r+" --> x="+x);
        //    return x;
        //}
    }
}